package leetcode;


import cn.hutool.core.date.StopWatch;

import java.util.concurrent.TimeUnit;

public class FibonacciDP {


    public static void main(String[] args) {
        StopWatch stopWatch = new StopWatch("basic");
//        stopWatch.start();
//        System.out.println(fibonacciDP_V1(50));
//        stopWatch.stop();
//
////
//        stopWatch.start();
//        System.out.println(fibonacciDP(50));
//        stopWatch.stop();



        stopWatch.start();
        System.out.println(fibonacciOptimized(50));
        stopWatch.stop();

        System.out.println(stopWatch.getLastTaskTimeNanos());


    }


    /**
     * 基础斐波那契数列解法：暴力递归求解第n个数字的值  ==> DFS搜索
     */

    public static long fibonacciDP(int n ) {
        if (n <= 1) return n;
        return fibonacciDP(n - 1) + fibonacciDP(n - 2);
    }



    /**
     * 基础斐波那契数列解法：动态规划优化===> 记忆法或者制表法
     */

    public static long fibonacciDP_V1(int n) {
        if (n <= 1) return n;
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];

        }
        return dp[n];
    }

    /**
     * 基础斐波那契数列解法：动态规划优化: 记忆法和指标法空间优化  ===> 空间优化DP：只保留最后两个值
     */
    public static long fibonacciOptimized(int n) {
        if (n <= 1) return n;

        long prev1 = 0;  // F(0)
        long prev2 = 1;  // F(1)

        for (int i = 2; i <= n; i++) {
            long current = prev1 + prev2;
            prev1 = prev2;  // 更新前两个值
            prev2 = current;
        }
        return prev2;
    }



    // 记忆化搜索：递归+缓存
    public static long fibonacciMemo(int n) {
        long[] memo = new long[n + 1];
        return fibHelper(n, memo);
    }

    private static long fibHelper(int n, long[] memo) {
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];  // 检查缓存

        memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
        return memo[n];
    }

}
